package com.yun.algorithmproblem.leetcode;

import java.util.HashMap;

public class Leetcode2597 {

    public static void main(String[] args) {
        Leetcode2597 obj = new Leetcode2597();
        int[] nums = {4, 2, 5, 9, 10, 3};
        int k = 1;
        System.out.println(obj.beautifulSubsets(nums, k));
    }

    int ans = 0;

    public int beautifulSubsets(int[] nums, int k) {
        dfs(0, nums, k, new HashMap<>());
        return ans;
    }

    private void dfs(int start, int[] nums, int k, HashMap<Integer, Integer> map) {
        if (start >= nums.length) {
            return;
        }
        //能不能选?
        if (map.containsKey(nums[start]) && map.get(nums[start]) != 0) {//不能选
            dfs(start + 1, nums, k, map);
        } else {//能选
            //选
            map.merge(nums[start] - k,1,Integer::sum);
            map.merge(nums[start] + k,1,Integer::sum);
            ans++;
            dfs(start + 1, nums, k, map);
            //不选
            map.merge(nums[start] - k,-1,Integer::sum);
            map.merge(nums[start] + k,-1,Integer::sum);
            dfs(start + 1, nums, k, map);
        }
    }
}
